package com.topInterview;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: huangzhigao
 * @Date: 2022/2/20 12:10
 */
public class leecode45_jump2 {
    public int jump(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }

        //在跳跃不超过step步的情况下，最右边界是cur
        int cur = 0;
        //到i位置最小跳几步
        int step = 0;
        //在跳跃不超过step+1步的情况下，最右不超过哪里
        int next = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i > cur) {
                step++;
                cur = next;
            }
            next = Math.max(next, i + nums[i]);

        }
        return step;
    }


    /**
     * 从start跳到end最小需要几步
     *
     * @param nums
     * @param start
     * @param end
     * @return
     */
    public int jumpFromStartToEnd(int[] nums, int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        HashMap<Integer, Integer> levelMap = new HashMap<>();
        levelMap.put(start, 0);
        queue.add(start);
        while (!queue.isEmpty()) {
            int index = queue.poll();
            int level = levelMap.get(index);
            if (index == end) {
                return level;
            }else {
                int left = index - nums[index];
                int right = index+nums[index];
                //往左跳
                if (left > 0 && !levelMap.containsKey(left)) {
                    queue.add(left);
                    levelMap.put(left, level + 1);
                }
                //往右
                if (right < nums.length && !levelMap.containsKey(right)) {
                    queue.add(right);
                    levelMap.put(right, level + 1);
                }
            }


        }
        return -1;
    }

}
